// https://leetcode.cn/problems/Jf1JuT/

// 题干：现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
//       给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
//      请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，
//      返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
//      字符串 s 字典顺序小于 字符串 t 有两种情况：
//      在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
//      如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

// 示例：输入：words = ["wrt","wrf","er","ett","rftt"]
//      输出："wertf"

// 碎语：分析题意是关键,先搜集信息，然后再来一次拓扑排序

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    unordered_map<char, unordered_set<char>> edges; // 邻接表来存储图
    unordered_map<char, int> in; // 统计入座
    bool check; // 处理边界情况
public:
    string alienOrder(vector<string>& words)
    {
        // 1.建图 + 初始化入度哈希表
        for (auto& s : words){
            for (auto ch : s){
                in[ch] = 0;
            }
        }

        int n = words.size(); check = false;
        for (int i = 0 ; i < n ; i++){
            for (int j = i + 1 ; j < n ; j++){
                add(words[i], words[j]);
                if (check) return "";
            }
        }

        // 2.拓扑排序
        queue<char> q;
        for (auto& [a, b] : in){
            if (!b) q.push(a);
        }

        string ret;
        while (q.size()){
            char t = q.front(); q.pop();
            ret += t;

            for (char ch : edges[t]){
                in[ch]--;
                if (!in[ch]) q.push(ch);
            }
        }

        // 3. 判断
        for (auto& [a, b] : in){
            if (b) return "";
        }

        return ret;
    }

    void add(string& s1, string& s2){
        int n = min(s1.size(), s2.size());
        int i = 0;

        for ( ; i < n ; i++){
            if (s1[i] != s2[i]){
                char a = s1[i], b = s2[i]; // a -> b
                if (!edges.count(a) || !edges[a].count(b)){
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }
        if (i == s2.size() && i < s1.size()) check = true;
    }
};

int main()
{
    Solution sol;
    vector<string> words = {"wrt", "wrf", "er", "ett", "rftt"};
    string order = sol.alienOrder(words);

    cout << "Alien Dictionary Order: " << order << endl;

    return 0;
}




